package com.cat.slidingWindow;

/**
 * @author cat
 * @description https://leetcode.cn/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-ii/description/
 * @create 2025/8/1 09:45
 * @since JDK17
 */

public class Solution24 {
    public long validSubstringCount(String word1, String word2) {
        int[] h = new int[26];
        long ans = 0;
        int n = word1.length(), m = word2.length(), cnt = m;
        for (int i = 0; i < m; i++) {   // 收集word2中的所有字符
            h[word2.charAt(i) - 'a']++;
        }
        for (int l = 0, r = 0; r < n; r++) {
            cnt -= h[word1.charAt(r) - 'a']-- > 0 ? 1 : 0;
            while (cnt <= 0) {  // 可以求答案了
                ans += n - r;
                cnt += h[word1.charAt(l++) - 'a']++ == 0 ? 1 : 0;
            }
        }
        return ans;
    }
}
